package com.practice.niuke.new_direct_basics.class05;

/**
 * 如何判断一颗二叉树是否是平衡二叉树？
 */
public class Code06_IsBalancedTree {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 判断一颗二叉树是否是平衡二叉树时，
     * 递归函数作用于每个节点返回的统一信息：
     * <f>
     * （1）boolean isBalanced: 整棵子树是否是平衡二叉树
     * （2）int height: 整棵子树的高度
     */
    public static class Info {
        public boolean isBalanced;
        public int height;

        public Info(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

    /**
     * 递归函数：以x为头的树，返回Info（2个信息）
     *
     * @param x 节点
     * @return Info
     */
    public static Info process(Node x) {
        if (x == null) {
            return new Info(true, 0);
        }
        // x节点的左子树（不包括x节点）返回的两个个信息
        Info leftInfo = process(x.left);
        // x节点的右子树（不包括x节点）返回的两个个信息
        Info rightInfo = process(x.right);

        // 以x节点为头的子树的高度
        // 以x节点为头的子树的高度：
        // x节点的左子树（不包括x节点）的高度 和 x节点的右子树（不包括x节点）的高度 的最大值 + 1（自己在子树的上一层）
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;

        // 求以x节点为头的子树是否为平衡二叉树:
        // x节点的左子树（不包括x节点）是平衡的 &&
        // x节点的右子树（不包括x节点）是平衡的 &&
        // x节点的左子树和右子树（不包括x节点）高度相差不超过1
        boolean isBalanced = leftInfo.isBalanced && rightInfo.isBalanced &&
                Math.abs(leftInfo.height - rightInfo.height) <= 1;

        return new Info(isBalanced, height);
    }

    /**
     * 判断一颗二叉树是否是平衡二叉树
     * (里面调用递归流程)
     *
     * @return boolean
     */
    public static boolean isBalanced(Node head){
        Info info = process(head);
        return info.isBalanced;
    }

}
